|
In graph theory, the bipartite double cover of an undirected graph ''G'' is a bipartite covering graph of ''G'', with twice as many vertices as ''G''. It can be constructed as the tensor product of graphs ''G'' × ''K''2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of ''G''. It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. ==Construction== The bipartite double cover of ''G'' has two vertices ''ui'' and ''wi'' for each vertex ''vi'' of ''G''. Two vertices ''ui'' and ''wj'' are connected by an edge in the double cover if and only if ''vi'' and ''vj'' are connected by an edge in ''G''. For instance, below is an illustration of a bipartite double cover of a non-bipartite graph ''G''. In the illustration, each vertex in the tensor product is shown using a color from the first term of the product (''G'') and a shape from the second term of the product (''K''2); therefore, the vertices ''ui'' in the double cover are shown as circles while the vertices ''wi'' are shown as squares. : The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a voltage graph in which each edge of ''G'' is labeled by the nonzero element of the two-element group. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「bipartite double cover」の詳細全文を読む スポンサード リンク
|